package com.ly.algorithm.leetcode.dp;

/**
 * @Classname Problem
 * @Description
 *
 * 示例 1:
 *
 * 输入: amount = 5, coins = [1, 2, 5]
 * 输出: 4
 * 解释: 有四种方式可以凑成总金额:
 * 5=5
 * 5=2+2+1
 * 5=2+1+1+1
 * 5=1+1+1+1+1
 * 示例 2:
 *
 * 输入: amount = 3, coins = [2]
 * 输出: 0
 * 解释: 只用面额2的硬币不能凑成总金额3。
 * 示例 3:
 *
 * 输入: amount = 10, coins = [10]
 * 输出: 1
 *
 * @Date 2020/12/24 19:31
 * @Author 冷心影翼
 */
public class Problem518 {

	public static void main(String[] args) {
		Solution518 solution518 = new Solution518();
		System.out.println(solution518.change(5, new int[]{1, 2, 5}));
	}

}


class Solution518 {
	public int change(int amount, int[] coins) {
		int[][] dp = new int[coins.length+1][amount+1];
		for (int i = 0; i <= coins.length; i++) {
			dp[i][0] = 1;
		}
		for (int i = 1; i <= coins.length; i++) {
			for (int j = 1; j <= amount; j++) {
				if(coins[i-1]>j) {
					dp[i][j] = dp[i-1][j];
				}else {
					dp[i][j] = dp[i-1][j]+dp[i][j-coins[i-1]];
				}
			}
		}
		return dp[coins.length][amount];
	}
}